6.9 KB · ⇊ 3 parts · ⤓ Micron 6.9 KB · ⤓ HTML 49.9 KB

top

Der Forward-Algorithmus (auch Vorwärts-Algorithmus, Vorwärts-Prozedur) berechnet mit Hilfe sogenannter Forward-Variablen für ein gegebenes Hidden-Markov-Modell die Wahrscheinlichkeit einer bestimmten Beobachtung. Er verwendet die Programmiermethode der dynamischen Programmierung.

• Markov-Modell

• Aufgabenstellung und Forward-Variablen

• Funktionsweise

• Komplexität

• Weitere Anwendungen

• Siehe auch

• Literatur

• Weblinks

Das Markov-Modell ist definiert als λ λ = ( S ; V ; A ; B ; π π ) {\displaystyle \lambda =(S;V;A;B;\pi )} , wobei

• S {\displaystyle S} die Menge der verborgenen Zustände,

• V {\displaystyle V} das Alphabet der beobachtbaren Symbole,

• A {\displaystyle A} die Matrix der Übergangswahrscheinlichkeiten,

• B {\displaystyle B} die Matrix der Emissionswahrscheinlichkeiten,

• π π {\displaystyle \pi } die Anfangsverteilung für die möglichen Anfangszustände,

bezeichnet.

Gegeben sei ein Wort o = o 1 o 2 … … o T ∈ ∈ V ∗ ∗ {\displaystyle {\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}} . Der Forward-Algorithmus berechnet nun P ( o | λ λ ) {\displaystyle P({\boldsymbol {o}}|\lambda )} , also die Wahrscheinlichkeit im vorhandenen Modell λ λ {\displaystyle \lambda } tatsächlich die Beobachtung o {\displaystyle {\boldsymbol {o}}} zu machen.

Dafür werden die Forward-Variablen α α t ( i ) {\displaystyle \alpha _{t}(i)} verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt 1 ≤ ≤ t ≤ ≤ T {\displaystyle 1\leq t\leq T} das Präfix o 1 o 2 … … o t {\displaystyle o_{1}o_{2}\ldots o_{t}} beobachtet zu haben und im Zustand s i ∈ ∈ S {\displaystyle s_{i}\in S} zu sein gespeichert:

α α t ( i ) = P ( o 1 o 2 … … o t ; q t = s i | λ λ ) {\displaystyle \alpha _{t}(i)=P(o_{1}o_{2}\ldots o_{t};q_{t}=s_{i}|\lambda )}

Die Forward-Variablen, und damit auch die Gesamtwahrscheinlichkeit, lassen sich rekursiv berechnen:

α α 1 ( i ) = π π i ⋅ ⋅ b i ( o 1 ) , 1 ≤ ≤ i ≤ ≤ | S | {\displaystyle \alpha _{1}(i)=\pi _{i}\cdot b_{i}(o_{1}),\qquad 1\leq i\leq \left|S\right|}

α α t ( i ) = ( ∑ ∑ j = 1 | S | α α t − − 1 ( j ) a j i ) ⋅ ⋅ b i ( o t ) ; 1 < t ≤ ≤ T , 1 ≤ ≤ i ≤ ≤ | S | {\displaystyle \alpha _{t}(i)=\left(\sum _{j=1}^{|S|}\alpha _{t-1}(j)a_{ji}\right)\cdot b_{i}(o_{t});\qquad 1<t\leq T,\ 1\leq i\leq \left|S\right|}

P ( o | λ λ ) = ∑ ∑ j = 1 | S | α α T ( j ) {\displaystyle P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{|S|}\alpha _{T}(j)}

Der Algorithmus benötigt O ( | S | 2 ⋅ ⋅ T ) {\displaystyle O(|S|^{2}\cdot T)} Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit. Der Speicherbedarf liegt in O ( | S | ⋅ ⋅ T ) {\displaystyle O(|S|\cdot T)} , da zur Erreichung der polynomiellen Laufzeit alle α α t ( i ) {\displaystyle \alpha _{t}(i)} in einer | S | × × T {\displaystyle |S|\times T} Matrix abgelegt werden.

Wenn die Zwischenergebnisse von α α t ( i ) {\displaystyle \alpha _{t}(i)} für t < T {\displaystyle t<T} nach der Beendigung der Rekursion nicht benötigt werden, dann reduziert sich der Speicherbedarf auf O ( | S | ) {\displaystyle O(|S|)} , da zwei Spaltenvektoren der Länge | S | {\displaystyle |S|} ausreichen um α α t − − 1 ( i ) {\displaystyle \alpha _{t-1}(i)} und α α t ( i ) {\displaystyle \alpha _{t}(i)} in jedem Rekursionsschritt zu speichern.

Die Forward-Variablen α α t ( i ) {\displaystyle \alpha _{t}(i)} werden zusammen mit den Backward-Variablen β β t ( i ) = P ( o t + 1 … … o T | q t = s i ; λ λ ) {\displaystyle \beta _{t}(i)=P(o_{t+1}\dots o_{T}|q_{t}=s_{i};\lambda )} für den Baum-Welch-Algorithmus zur Lösung des mit Hidden-Markov-Modellen gegebenen Lernproblems benötigt.

Außerdem ermöglicht deren Kenntnis die Bestimmung der Wahrscheinlichkeit, bei der Beobachtung von o {\displaystyle {\boldsymbol {o}}} zu einem festen Zeitpunkt t {\displaystyle t} im Zustand s i {\displaystyle s_{i}} gewesen zu sein, denn nach dem Satz von Bayes gilt:

P ( q t = s i | o ; λ λ ) = α α t ( i ) ⋅ ⋅ β β t ( i ) P ( o | λ λ ) {\displaystyle P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}}

• Backward-Algorithmus

• Viterbi-Algorithmus

• Baum-Welch-Algorithmus

• R. Durbin et al.: Biological sequence analysis. Probabilistic models of proteins and nucleic acids. 11th printing, corrected 10. reprinting. Cambridge University Press, Cambridge u. a. 2006, ISBN 0-521-62971-3, S. 59.

• E. G. Schukat-Talamazzini: Spezielle Musteranalysesysteme (PDF, 1,3 MB) Vorlesung im WS 2012/13 an der Universität Jena. Kapitel 5 Folie 32ff.